﻿///////////////////////////////////////////////////////////////////////////////
//
//  This source is part of the  "Managed Task Framework.NET Runtime"  (MTF.NET Runtime).
//
//
//  Copyright (c) 2011, Multicore Consulting Limited (UK)
//  All rights reserved.
//  http://www.multicoreconsulting.co.uk
//
//  Redistribution and use in source and binary forms, with or without
//  modification, are permitted provided that the following conditions
//  are met:
//
//  -  Redistributions of source code must retain the above copyright
//     notice, this list of conditions and the following disclaimer.
//  -  Redistributions in binary form must reproduce the above copyright
//     notice, this list of conditions and the following disclaimer in
//     the documentation and/or other materials provided with the
//     distribution.
//  -  Neither the name of Multicore Consulting Limited nor the names of
//     its contributors may be used to endorse or promote products
//     derived from this software without specific prior written
//     permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
//  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
//  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
//  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
//  COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
//  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
//  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
//  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
//  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
//  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
//  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
//  POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace MTFOrg.MTF.MTFCore
{
    /// <summary>
    /// Fixed size sequenced queue.
    /// </summary>
    public class SequencedQueue<T>
    {
        /// <summary>
        /// Items held in the queue.
        /// </summary>
        protected T[] m_Items;

        /// <summary>
        /// Skip flag for each position in the array
        /// </summary>
        protected bool[] m_Skip;

        /// <summary>
        /// Index to read from.
        /// </summary>
        protected int m_ReadIndex;

        /// <summary>
        /// Index to write at.
        /// </summary>
        protected int m_WriteIndex;

        /// <summary>
        /// Number of items available to read.
        /// </summary>
        protected int m_NumAvailItems;

        /// <summary>
        /// Whether to enforce write ordering.
        /// </summary>
        protected bool m_IsOrdered;

        /// <summary>
        /// Adds an item to the queue, in sequence order.
        /// </summary>
        /// <param name="item">Item to add</param>
        /// <param name="seqNum">Sequence number</param>
        public void Enqueue(T item, int seqNum)
        {
            if (!m_IsOrdered)
            {
                m_Items[m_WriteIndex] = item;
                m_WriteIndex++;
                if (m_WriteIndex == m_Items.Length)
                    m_WriteIndex = 0;
                m_NumAvailItems++;
            }
            else
            {
                int position = seqNum % m_Items.Length;
                Debug.Assert(m_Items[position] == null, "Attempt to overwrite existing queue item");

                // Add item
                m_Items[position] = item;
                m_Skip[position] = false;

                // Recalculate number of available items and write index.
                while (m_NumAvailItems < m_Items.Length)
                {
                    if (m_Items[m_WriteIndex] != null)
                    {
                        m_NumAvailItems++;
                        m_WriteIndex++;
                        if (m_WriteIndex == m_Items.Length)
                            m_WriteIndex = 0;
                    }
                    else if (m_Skip[m_WriteIndex])
                    {
                        m_WriteIndex++;
                        if (m_WriteIndex == m_Items.Length)
                            m_WriteIndex = 0;
                    }
                    else break;
                }
            }

#if SQUEUE_TRACE
            string qdata = string.Empty;
            for (int i = 0; i < m_Items.Length; i++)
                if (m_Items[i] != null) qdata += " X";
                else qdata += " -";
            Debug.WriteLine("ENQ: " + qdata + " W" + m_WriteIndex.ToString() + " R" + m_ReadIndex.ToString());
#endif
        }

        public void Prequeue(T item)
        {
            m_ReadIndex--;
            if (m_ReadIndex < 0) m_ReadIndex = m_Items.Length - 1;

            // Add item
            m_Items[m_ReadIndex] = item;
        }

        /// <summary>
        /// Removes an item from the front of the queue.
        /// </summary>
        /// <returns>Item from front of queue</returns>
        public T Dequeue()
        {
            Debug.Assert(m_NumAvailItems > 0, "Attempt to remove item from empty queue");
            T item = m_Items[m_ReadIndex];
            m_Items[m_ReadIndex] = default(T);
            do
            {
                m_ReadIndex++;
                if (m_ReadIndex == m_Items.Length) m_ReadIndex = 0;
            } while (m_Skip[m_ReadIndex]);
            m_NumAvailItems--;

            return item;
        }

        public void Skip(int seqNum)
        {
            if (m_IsOrdered)
            {
                int position = seqNum % m_Items.Length;

                // Mark location as skipped
                m_Skip[position] = true;

                // Advance read index past skipped locations
                if (position == m_ReadIndex)
                {
                    do
                    {
                        m_ReadIndex++;
                        if (m_ReadIndex == m_Items.Length) m_ReadIndex = 0;
                    } while (m_Skip[m_ReadIndex]);
                }
            }
        }

        /// <summary>
        /// Peeks at an item from the front of the queue without removing it.
        /// </summary>
        /// <returns>Item from front of queue</returns>
        public object Peek()
        {
            Debug.Assert(m_NumAvailItems > 0, "Attempt to peek item from empty queue");

            return m_Items[m_ReadIndex];
        }

        /// <summary>
        /// Gets the count of items that are available.
        /// </summary>
        public int Count
        {
            get { return m_NumAvailItems; }
        }

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="size">Maximum number of items in the queue</param>
        /// <param name="isOrdered">Whether to enforce write ordering</param>
        public SequencedQueue(int size, bool isOrdered)
        {
            m_Items = new T[size];
            m_Skip = new bool[size];
            m_ReadIndex = 0;
            m_WriteIndex = 0;
            m_NumAvailItems = 0;
            m_IsOrdered = isOrdered;
        }
    }
}